/** @internal */
namespace ts {
    export function createGetSymbolWalker(
        getRestTypeOfSignature: (sig: Signature) => Type,
        getReturnTypeOfSignature: (sig: Signature) => Type,
        getBaseTypes: (type: Type) => Type[],
        resolveStructuredTypeMembers: (type: ObjectType) => ResolvedType,
        getTypeOfSymbol: (sym: Symbol) => Type,
        getConstraintOfTypeParameter: (typeParameter: TypeParameter) => Type | undefined,
        getTypeArguments: (type: TypeReference) => readonly Type[]) {

        return getSymbolWalker;

        function getSymbolWalker(accept: (symbol: Symbol) => boolean = () => true): SymbolWalker {
            const visitedTypes: Type[] = []; // Sparse array from id to type
            const visitedSymbols: Symbol[] = []; // Sparse array from id to symbol

            return {
                walkType: type => {
                    try {
                        visitType(type);
                        return { visitedTypes: getOwnValues(visitedTypes), visitedSymbols: getOwnValues(visitedSymbols) };
                    }
                    finally {
                        clear(visitedTypes);
                        clear(visitedSymbols);
                    }
                },
                walkSymbol: symbol => {
                    try {
                        visitSymbol(symbol);
                        return { visitedTypes: getOwnValues(visitedTypes), visitedSymbols: getOwnValues(visitedSymbols) };
                    }
                    finally {
                        clear(visitedTypes);
                        clear(visitedSymbols);
                    }
                },
            };

            function visitType(type: Type | undefined): void {
                if (!type) {
                    return;
                }

                if (visitedTypes[type.id]) {
                    return;
                }
                visitedTypes[type.id] = type;

                // Reuse visitSymbol to visit the type's symbol,
                //  but be sure to bail on recuring into the type if accept declines the symbol.
                const shouldBail = visitSymbol(type.symbol);
                if (shouldBail) return;

                // Visit the type's related types, if any
                if (type.flags & TypeFlags.Object) {
                    const objectType = type as ObjectType;
                    const objectFlags = objectType.objectFlags;
                    if (objectFlags & ObjectFlags.Reference) {
                        visitTypeReference(type as TypeReference);
                    }
                    if (objectFlags & (ObjectFlags.Class | ObjectFlags.Interface)) {
                        visitInterfaceType(type as InterfaceType);
                    }
                    if (objectFlags & (ObjectFlags.Anonymous)) {
                        visitObjectType(objectType);
                    }
                }
                if (type.flags & TypeFlags.TypeParameter) {
                    visitTypeParameter(type as TypeParameter);
                }
                if (type.flags & TypeFlags.UnionOrIntersection) {
                    visitUnionOrIntersectionType(type as UnionOrIntersectionType);
                }
            }

            function visitTypeReference(type: TypeReference): void {
                visitType(type.target);
                forEach(getTypeArguments(type), visitType);
            }

            function visitTypeParameter(type: TypeParameter): void {
                visitType(getConstraintOfTypeParameter(type));
            }

            function visitUnionOrIntersectionType(type: UnionOrIntersectionType): void {
                forEach(type.types, visitType);
            }

            function visitSignature(signature: Signature): void {
                forEach(signature.typeParameters, visitType);

                for (const parameter of signature.parameters) {
                    visitSymbol(parameter);
                }
                visitType(getRestTypeOfSignature(signature));
                visitType(getReturnTypeOfSignature(signature));
            }

            function visitInterfaceType(interfaceT: InterfaceType): void {
                visitObjectType(interfaceT);
                forEach(interfaceT.typeParameters, visitType);
                forEach(getBaseTypes(interfaceT), visitType);
                // visitType(interfaceT.thisType);
            }

            function visitObjectType(type: ObjectType): void {
                // The two checks above *should* have already resolved the type (if needed), so this should be cached
                const resolved = resolveStructuredTypeMembers(type);
                for (const signature of resolved.callSignatures) {
                    visitSignature(signature);
                }
                for (const p of resolved.properties) {
                    visitSymbol(p);
                }
            }

            function visitSymbol(symbol: Symbol | undefined): boolean {
                if (!symbol) {
                    return false;
                }
                const symbolId = getSymbolId(symbol);
                if (visitedSymbols[symbolId]) {
                    return false;
                }
                visitedSymbols[symbolId] = symbol;
                if (!accept(symbol)) {
                    return true;
                }
                const t = getTypeOfSymbol(symbol);
                visitType(t); // Should handle members on classes and such
                if (symbol.members) {
                    symbol.members.forEach(visitSymbol);
                }
                return false;
            }
        }
    }
}